class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        int ans = 1000000000,left = 0,sum = 0;
        for(int right = 0;right < n;right++){
            sum += nums[right];
            while(sum >= target){
                ans = min(ans, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }
        if(ans == 1000000000) return 0;
        return ans;
        
    }
};
class Solution {
public:
    string shortestBeautifulSubstring(string s, int k) {
        int n = s.size(), ans1 = 0, ans2 = 1000000, left = 0;
        string ans(1000,'1');
        for (int right = 0; right < n; right++) {
            if (s[right] == '1')
                k--;
            while (k == 0) {
                string tmp = s.substr(left, right - left + 1);

                if (right - left + 1 < ans.size()) {
                    ans = tmp;
                }else if(right - left + 1 == ans.size()){
                    ans = min(ans,tmp);
                }
                if (s[left] == '1')
                    k++;
                left++;
            }
        }
        if (ans == string(1000,'1'))
            return "";
        return ans;
    }
};
bool fun(vector<int>& window,int n){
    n/=4;
    return window['Q'] <= n && window['W'] <= n && window['E'] <= n && window['R'] <= n; 
}
class Solution {
public:
    int balancedString(string s) {
        vector<int> window(256);
        for(auto e : s) window[e]++;
        int n = s.size(),left = 0,right = 0,ret = 10000000000;
        // vector<int> chwindow(256);
        if(fun(window,n))
            return 0;
        for(;right < n;right++){
            //chwindow[s[right]]++;
            window[s[right]]--;
            while(left <= right && fun(window,n))
            {
                ret = min(ret,right - left + 1);
                window[s[left]]++;
                left++;
                // cout << left  << endl;
                // if(left == n) return 0;
            }
        }
        return min(ret,(int)s.size());
    }
    class Solution {
public:
    int minSizeSubarray(vector<int>& nums, int target) {
        int n = nums.size(),ans = 100000000, left = 0,right = 0,sum = 0;
        bool t[2] = {true,true};
        for(int i = 0;i < n;i++)
        {
            if(nums[i] != 0)
                t[0] = false;
            if(nums[i] != 1)
                t[1] = false;
        }
        if(t[0]) return -1;
        if(t[1]) return target;
        while(1)
        {
            sum += nums[right%n];
            // cout << right <<' '<<sum <<endl;
            while(sum > target)
            {
                sum -= nums[left%n];
                left++;
            }
            if(sum == target){
                ans = min(ans,right - left + 1);
            }
            if(left >= n){
                if(ans == 100000000) return -1;
                return ans;
            }
            right++;
        }
        return -1;
    }
};
};
class Solution {
public:
    int findLengthOfShortestSubarray(vector<int>& arr) {
        int n = arr.size(), ans = 0, tmp = 0, tleft = 1, tright = 1;
        for (int i = 1; i < n; i++) {
            if (arr[i] >= arr[i - 1])
                tleft++;
            else
                break;
        }
        for (int i = n - 2; i >= 0; i--) {
            if (arr[i] <= arr[i + 1])
                tright++;
            else
                break;
        }
        // cout << tright << ' ' << tleft << endl;
        ans = min(n - tright, n - tleft);
        // cout <<  ans << endl;
        if(arr[tleft - 1] <= arr[n - tright]) return max(n - tleft - tright,0);
        if(tleft == 1 || tright == 1 || ans == 0) return ans;
        int right = n - tright;
        for (int left = 0; left < tleft; left++) {
            while (right < n && arr[left] > arr[right]) {
                right++;
            }
            ans = min(ans, max(right - left - 1,0));
            //cout << left << ' ' << right << ' ' << ans << endl;
        }
        return ans;
    }
};
bool fun(vector<int>& window) {
    for (int i = 'a'; i <= 'z'; i++) {
        if (window[i] > 0)
            return false;
    }
    for (int i = 'A'; i <= 'Z'; i++) {
        if (window[i] > 0)
            return false;
    }
    return true;
}
class Solution {
public:
    string minWindow(string s, string t) {
        vector<int> window(256);
        for (auto e : t)
            window[e]++;
        int n = s.size(), retleft = 0, retright = 10000000, left = 0, right = 0;
        for (; right < n; right++) {
            window[s[right]]--;
            while (fun(window)) {
                if (retright - retleft > right - left) {
                    retright = right;
                    retleft = left;
                }
                window[s[left]]++;
                left++;
            }
        }
        if (retright == 10000000)
            return "";
        return s.substr(retleft, retright - retleft + 1);
    }
};
bool fun(vector<vector<int>>& nums, int left, int right) {
    for (vector<int>& vv : nums) {
        int n = vv.size();
        bool t = false;
        for (int i = 0; i < n; i++) {
            if (vv[i] >= left && vv[i] <= right) {
                t = true;
                break;
            }
        }
        if (t == false)
            return false;
    }
    return true;
}
class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        map<int, int> window;
        for (auto& ee : nums) {
            for (auto e : ee) {
                window[e]++;
                if (window[e] == nums.size())
                    return {e, e};
            }
        }

        auto pleft = window.begin(), pright = window.begin();
        int retleft = 0, retright = 10000000,sum = 0;
        for (; pright != window.end(); pright++) {
            while (fun(nums, pleft->first, pright->first)) {
                sum += 
                if (retright - retleft > pright->first - pleft->first)
                    retright = pright->first, retleft = pleft->first;
                if (retright == retleft)
                    return {retleft, retright};
                pleft++;
            }
        }
        return {retleft, retright};
    }
};
bool fun(pair<int, int>& a, pair<int, int>& b) { return a.first < b.first; }
bool fun2(vector<int>& window) {
    for (auto e : window)
        if (e == 0)
            return false;
    return true;
}
class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        vector<pair<int, int>> vv;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < nums[i].size(); j++) {
                vv.emplace_back(make_pair(nums[i][j], i));
            }
        }
        sort(vv.begin(), vv.end(), fun);
        vector<int> window(n);
        int left = 0, right = 0, rleft = 0, rright = 1000000, size = vv.size();
        for (; right < size; right++) {
            window[vv[right].second]++;
            while (fun2(window)) {
                if (rright - rleft > vv[right].first - vv[left].first)
                    rright = vv[right].first, rleft = vv[left].first;
                window[vv[left].second]--;
                left++;
            }
        }
        return {rleft,rright};
    }
};